package ljl.alg.wangzheng_camp.round1.backtrack;

import java.util.ArrayList;
import java.util.List;

public class _216_combination_sum {
    
    static class backtrack1 {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        public List<List<Integer>> combinationSum3(int k, int n) {
            backtrack(k, 1, 9, 0, n);
            return res;
        }
        void backtrack(int k, int idx, int n, int currentSum, int sum) {
            if (path.size() + n - idx + 1 < k || path.size() > k) return;
            if (path.size() == k) {
                if (currentSum == sum)
                    res.add(new ArrayList<>(path));
                return;
            }
            backtrack(k, idx + 1, n, currentSum, sum);
            path.add(idx);
            backtrack(k, idx + 1, n, currentSum + idx, sum);
            path.remove(path.size() - 1);
        }
    }
    
    /**
     * 我以为有什么妙招原来是枚举 1 << 9 这么些个数我丢？
     *
     * 每次 clear 比每次 new 要快。因为 check 的次数远远大于符合要求的结果，所以
     * 还是 clear 比较省内存！
     * */
    static class bitwise {
        List<Integer> temp = new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
    
        public List<List<Integer>> combinationSum3(int k, int n) {
            for (int i = 3, limit = 1 << 9; i < limit; i++) {
                if (check(i, k, n))
                    res.add(new ArrayList<>(temp));
            }
            return res;
        }
        boolean check(int num, int k, int n) {
            temp.clear();
            for (int i = 0; i < 9; i++) {
                if ((num & (1 << i)) != 0)
                    temp.add(i + 1);
            }
            if (temp.size() != k) return false;
            int sum = 0;
            for (int each : temp) {
                sum += each;
            }
            return sum == n;
        }
    }
    
    class Solution {
        List<Integer> temp = new ArrayList<Integer>();
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        
        public List<List<Integer>> combinationSum3(int k, int n) {
            for (int mask = 0; mask < (1 << 9); ++mask) {
                if (check(mask, k, n)) {
                    ans.add(new ArrayList<Integer>(temp));
                }
            }
            return ans;
        }
        
        public boolean check(int mask, int k, int n) {
            temp.clear();
            for (int i = 0; i < 9; ++i) {
                if (((1 << i) & mask) != 0) {
                    temp.add(i + 1);
                }
            }
            if (temp.size() != k) {
                return false;
            }
            int sum = 0;
            for (int num : temp) {
                sum += num;
            }
            return sum == n;
        }
    }
    
}
